1. Field of the Invention
This invention relates to a sort accelerator and more particularly to a sort accelerator in which a rebound sorter is used as a merger and with which large numbers of records can be rapidly and efficiently sorted. The accelerator of the invention operates independently of a host computer and is highly reliable, while using a minimum number of components and being otherwise economically manufacturable.
2. Background of the Prior Art
Pipelined VLSI implementations of sorting algorithms are known. A rebound sorter developed by IBM includes a set of processing elements which can be visualized as forming a U-shaped pipeline with data flowing down along a left side and up along a right side. The processing elements operate concurrently to speed up the sorting process. Each element effects a comparison of data from two records and, depending upon the results of the comparison, effects either vertical movements down along the left side and up along the right side or horizontal exchanges such that "heavier" records are moved to the left and downwardly while "lighter" records move to the right and upwardly to eventually exit the upper end of the right side in sorted order. Rebound sorters of this type have advantages in speeding up sorting operations, but the cost of the required hardware has precluded extensive use of such sorters, particularly for sorting large numbers of records.
Other types of sorting systems have been proposed, using multiple processing elements. All known types of systems have limitations, however, particularly with respect to operating speed, hardware costs, stability and reliability.